Find all numbers disappeared in an array

Time: O(N); Space: O(1); easy

Given an array of integers where 1 <= a[i] <= N (N = size of array), some elements appear twice and others appear once.

Find all the elements of [1, N] inclusive that do not appear in this array.

Could you do it without extra space and in O(N) runtime? You may assume the returned list does not count as extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Hints:

  1. This is a really easy problem if you decide to use additional memory. For those trying to write an initial solution using additional memory, think counters!

  2. However, the trick really is to not use any additional space than what is already available to use. Sometimes, multiple passes over the input array help find the solution. However, there’s an interesting piece of information in this problem that makes it easy to re-use the input array itself for the solution.

  3. The problem specifies that the numbers in the array will be in the range [1, N] where N is the number of elements in the array. Can we use this information and modify the array in-place somehow to find what we need?

[1]:

class Solution1(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            if nums[abs(nums[i]) - 1] > 0:
                nums[abs(nums[i]) - 1] *= -1

        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                result.append(i+1)
            else:
                nums[i] *= -1
        return result

[2]:

s = Solution1()
assert s.findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1]) == [5, 6]

[3]:

class Solution2(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return list(set(range(1, len(nums) + 1)) - set(nums))

[4]:

s = Solution2()
assert s.findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1]) == [5, 6]

[8]:

class Solution3(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            index = abs(nums[i]) - 1
            nums[index] = - abs(nums[index])

        return [i + 1 for i in range(len(nums)) if nums[i] > 0]

[9]:

s = Solution3()
assert s.findDisappearedNumbers([4, 3, 2, 7, 8, 2, 3, 1]) == [5, 6]